package com.its.myalgorithm.day04;

/**
 * @projectName: dgl-algorithm
 * @package: com.its.myalgorithm.day04
 * @className: AddTwoNumbers
 * @author: DONG GL
 * @description: TODO  测试链接：https://leetcode.com/problems/add-two-numbers/
 *
 * 两个链表相加问题 给定两个链表的头节点head1和head2， 认为从左到右是某个数字从低位到高位，返回相加之后的链表
 * 例子 4 -> 3 -> 6 2 -> 5 -> 3 返回 6 -> 8 -> 9 解释 634 + 352 = 986
 * @date: 2022/4/3 17:10
 * @version: 1.0
 */
public class AddTwoNumbers {

    /**
     * 两数之和
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int head1Length = getListLength(l1);
        int head2Length = getListLength(l2);
        //长链表
        ListNode l = head1Length >= head2Length ? l1 : l2;
        //短链表
        ListNode s = l == l1 ? l2 : l1;
        ListNode last = l;
        ListNode SCurNode = s;
        ListNode LCurNode = l;
        //当前节点和
        int curNum = 0;
        //进位信息
        int carry = 0;
        //处理短链表
        while (SCurNode != null) {
            //当前短节点+ 当前长节点
            curNum = SCurNode.val + LCurNode.val;
            //把值压入长节点中
            LCurNode.val = (curNum % 10);
            //计算进位信息
            carry = curNum / 10;
            //当前节点
            last = LCurNode;
            SCurNode = SCurNode.next;
            LCurNode = LCurNode.next;

        }

        //处理长链表
        while (LCurNode != null) {
            curNum = LCurNode.val + carry;
            LCurNode.val = curNum % 10;
            carry = curNum / 10;
            last = LCurNode;
            LCurNode = LCurNode.next;
        }
        //处理高位的进位信息 如果大于0则 需要在当前 last节点上面添加一个node
        if (carry != 0) {
            last.next = new ListNode(carry);
        }
        return l;
    }

    /**
     * 获取链表长度
     *
     * @param head
     * @return
     */
    public static int getListLength(ListNode head) {
        int len = 0;
        while (head.next != null) {
            len++;
        }
        return len;
    }

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
